package leetcode.test;

import java.sql.Array;
import java.util.*;
import java.util.stream.Stream;

public class ArrayAlgorithm {

    public static void main(String[] args) {
        ArrayAlgorithm ag = new ArrayAlgorithm();
//        ListNode listNode = new ListNode(1, new ListNode(2, new ListNode(3,null)));
//        ag.printStack1(listNode);
//        ListNode lst = ag.reverseList(listNode);
//        ag.printStack1(lst);
        System.out.println(ag.replaceSpace("i am liming"));
        //
        /**
         * 栈如何打印
         * m1 遍历
         */

    }



    public int[] reversePrint(ListNode head) {
        List<Integer> ls = new ArrayList<>();
        while( head != null){
            ls.add(head.val);
            head = head.next;
        }

        return new int[2];
    }

    /**
     * 请实现一个函数，把字符串 s 中的每个空格替换成"%20"。
     * 输入：s = "We are happy."
     * 输出："We%20are%20happy."
     */
    public String replaceSpace(String s) {
        StringBuffer sf = new StringBuffer();
        char[] chars = s.toCharArray();
        for (char c : s.toCharArray()) {
            if (c == ' ') {
                sf.append("%20");
            }else {
                sf.append(c);
            }
        }
        return sf.toString();
    }

    public String replaceSpace2(String s) {
        StringBuffer sf = new StringBuffer();
        char[] chars = s.toCharArray();
        for (char c : s.toCharArray()) {
            if (c == ' ') {
                sf.append("%20");
            }else {
                sf.append(c);
            }
        }
        return sf.toString();
    }

    public int[] twoSum2(int[] nums, int target) {
        Hashtable<Integer, Integer> hash = new Hashtable<>();
        for (int i = 0; i < nums.length; i++) {
            // target - nums[i]
            if (hash.containsKey(target - nums[i])) {
                return new int[]{hash.get(target - nums[i]), i};
            }
//            hash.put()
        }
        return new int[]{};
    }
    public int[] twoSum1(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i+1; j < nums.length; j++) {
                // 1 2 3 4 5
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        return new int[]{};
    }

    /**
     * 给定两个字符串形式的非负整数 num1 和num2，计算它们的和并同样以字符串形式返回。
     *
     * 你不能使用任何內建的用于处理大整数的库（比如 BigInteger），也不能直接将输入的字符串转换为整数形式。
     */
    public String addStrings(String num1, String num2) {

        return "";
    }

    public void printStack1(ListNode head){
        ListNode current = head;
        while (current != null) {
            System.out.print(current.val + " ");
            current = current.next;
        }
        System.out.println();
    }
    // have bug
    public void printStack2(ListNode head){
        while (head != null) {
            System.out.println(head.val);
            head = head.next;
            if (head == null) {
                break;
            }
        }
    }

    static public class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    /**
     * 链表反转法一 ：双链表
     */
    public void reverseList2(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        ListNode tmp = null;
        while (cur != null) {
            tmp = cur.next;
            cur.next = pre;
            pre =cur;
            cur = tmp;
        }
        return;
    }

    /**
     * 链表反转法二-栈
     * have bug
     */
    public ListNode reverseList(ListNode head) {
        Stack<ListNode> sk = new Stack<>();
        if (head == null) {
            return null;
        }
        while (head != null) {
            sk.add(head);
            head = head.next;
        }
        ListNode newHd = sk.pop();
        while(!sk.empty()){
            newHd.next = sk.pop();
        }
        return newHd;
    }

    /** 931. 下降路径最小和
     * 给你一个 n x n 的 方形 整数数组 matrix ，请你找出并返回通过 matrix 的下降路径 的 最小和 。
     * @param matrix
     * @return
     */
    public int minFallingPathSum(int[][] matrix) {
        int n = matrix.length;
        int[][] dp = new int[n][n];
        System.arraycopy(matrix[0], 0, dp[0], 0, n);
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int mn = dp[i - 1][j];
                if (j > 0) {
                    mn = Math.min(mn, dp[i - 1][j - 1]);
                }
                if (j < n - 1) {
                    mn = Math.min(mn, dp[i - 1][j + 1]);
                }
                dp[i][j] = mn + matrix[i][j];
            }
        }
        return Arrays.stream(dp[n - 1]).min().getAsInt();
    }
    public int minFallingPathSum2(int[][] matrix) {

        return 0;
    }

    /**
     * 2544. 交替数字和
     * 输入：n = 521
     * 输出：4
     * 解释：(+5) + (-2) + (+1) = 4
     */
    public int alternateDigitSum(int n) { // 21
        String s = String.valueOf(n);
        int len = s.length(); // 2
        int sum = 0;
        for (int i = 0; i < len; i++) {
            if (i % 2 == 0) {
                sum = sum + n / 10^(len - 1-i); // 21%10^(i+1)
            }else {
                sum = sum  -n % 10^(len - 1-i);;
            }
            n = n % 10 ^ (len - 1 - i);
        }
        return sum;
    }

    public int alternateDigitSum2(int n) { // 21
        String s = String.valueOf(n);
        int len = s.length();
        int[] n1 = new int[len];
        int ret = 0;
        for (int i = 0; i < len; i++) {
            int mid = Integer.parseInt(s.substring(i, i + 1));
            if (i % 2 == 0) {
                ret += mid;
            }else{
                ret -= mid;
            }
        }
        return ret;
    }
    public int alternateDigitSum3(int n) { // 21
        int res = 0, sign = 1;
        while (n > 0) {
            res += n % 10 * sign;
            sign = -sign;
            n /= 10;
        }
        return -sign * res;
//        return 0;
    }

    /**
     * 输入：finalSum = 12
     * 输出：[2,4,6]
     * 解释：以下是一些符合要求的拆分：(2 + 10)，(2 + 4 + 6) 和 (4 + 8) 。
     * (2 + 4 + 6) 为最多数目的整数，数目为 3 ，所以我们返回 [2,4,6] 。
     * [2,6,4] ，[6,2,4] 等等也都是可行的解。
     *
     * 8 【 2，4，6，8】 {2，6}
     * 12 【2，4，6，8，12】 2，4，6
     *
     * 16 【 2 4 6 8 10 12 14 16】 {2 6 8，}
     * 28 【2 4 6 8 10 12 14 16 18 20 22 24 26 28】{2 4 6 16，2 4 10 12，2 6 8 12，}
     *
     *
     */
    public List<Long> maximumEvenSplit(long finalSum) {
        List<Long> lst = new ArrayList();
        if (finalSum % 2 != 0) {
            return lst;
        }
        for (long i = 2; i <= finalSum; i+=2) {
            lst.add(i);
            finalSum  -= i;
        }
        int lastIndex = lst.size() - 1;
        lst.set(lastIndex, lst.get(lastIndex)+ finalSum);
        return lst;
    }

    public int kItemsWithMaximumSum2(int numOnes, int numZeros, int numNegOnes, int k) {
        if (k <= numOnes) {
            return k;
        } else if (k <= numOnes + numZeros) {
            return numOnes;
        } else {
            return numOnes - (k - numOnes - numZeros);
        }
    }

    public int kItemsWithMaximumSum(int numOnes, int numZeros, int numNegOnes, int k) {
        int ret = 0;
        /**
         * k < ones = k
         * k > ones and k < ones + zeros = ones
         * k > ones + zeros = ones - negOnes
         * {1，1，1，0，0，-1，-1} 3,2,2 k=6,s=2
         */
        if (k <= numOnes) {
            return k;
        } else if (k <= numOnes + numZeros) {
            return numOnes;
        }else {
            return numOnes - numNegOnes; // 3 - (6-3-2) = 2|| 3- 2 = 1
        }
    }

    /**
     * 2679. 矩阵中的和
     * 给你一个下标从 0开始的二维整数数组nums。一开始你的分数为0。你需要执行以下操作直到矩阵变为空：
     *
     * 矩阵中每一行选取最大的一个数，并删除它。如果一行中有多个最大的数，选择任意一个并删除。
     * 在步骤 1 删除的所有数字中找到最大的一个数字，将它添加到你的 分数中。
     * 请你返回最后的 分数。
     */
    int[][] nums = {{7,2,1},{6,4,2},{6,5,3},{3,2,1}};
    public int matrixSum(int[][] nums) {
        int res = 0;
        int m = nums.length;
        int n = nums[0].length;
        for (int i = 0; i < m; i++) {
            Arrays.sort(nums[i]);
        }
        for (int i = 0; i < n; i++) {
            int maxVal = 0;
            for (int j = 0; j < m; j++) {
                maxVal = Math.max(maxVal,nums[j][i]);
            }
            res += maxVal;
        }
        System.out.println(res);
        return res;
    }

    public int matrixSum2(int[][] nums) {
        int r = nums.length; //4
        int c = nums[0].length; //3
        for (int i = 0; i< c; i++){
            for (int j = 0; j < r-1; j++) {
                if(nums[j][i] < nums[j+1][i]){
                    int tmp = nums[j + 1][i];
                    nums[j + 1][i] = nums[j][i];
                    nums[j][i] = tmp;
                }
            }
        }
        int ret = Arrays.stream(nums[0]).sum();
        System.out.println("result: " + ret);
        return ret;
    }
}
